\chapter{Algorytm PSO}
\thispagestyle{fancy}
\section{Opis algorytmu}
Działanie algorytmu PSO opiera się na jednoczesnym utrzymywaniu kilku kandydujących rozwiązań w przestrzeni poszukiwań. Podczas każdej iteracji, każde kandydujące rozwiązanie jest ewaluowane przez funkcję celu i optymalizowane, przy jednoczesnym określeniu przydatności tego rozwiązania. Każde kandydujące rozwiązanie może być postrzegane jako "latająca" cząstka po obszarze dopasowania znajdując maksimum lub minimum funkcji celu.

Początkowo algorytm PSO wybiera rozwiązanie kandydujące losowo w obszarze poszukiwań.
Każda cząstka utrzymuje swoją pozycję składającą się z kandydujących rozwiązań, obliczonego  dopasowania i jej prędkości. Dodatkowo, cząstka pamięta najlepszą wartość dopasowania jaką uzyskała od początku działania algorytmu, określoną jako najlepsze indywidualne dopasowanie albo najlepsze indywidualne rozwiązanie kandydujące. Ostatecznie, algorytm PSO utrzymuje najlepszą uzyskaną wartość dopasowania wśród wszystkich cząstek roju, określoną jako najlepsze globalne dopasowanie. Rozwiązanie kandydujące, które osiągnęło takie dopasowanie, jest nazywane najlepszym globalnym rozwiązaniem kandydującym lub najlepszą globalną pozycją.\\

Algorytm PSO składa się z trzech kroków, powtarzanych do spełnienia warunku stopu.

\begin{enumerate}
\item Oblicz dopasowanie każdej cząstki
\item Zaktualizuj najlepsze indywidualne i globalne dopasowanie i pozycję
\item Zaktualizuj prędkość i pozycję każdej cząstki
\end{enumerate}

Dwa pierwsze kroki są dosyć proste. Dopasowanie oblicza się przy pomocy dostarczenia rozwiązań kandydujących do funkcji celu. Najlepsze indywidualne i globalne dopasowania i pozycje są aktualizowane poprzez porównanie nowo obliczonego dopasowania z najlepszymi dopasowaniami: indywidualnym i globalnym, podmieniając je, jeżeli jest to konieczne.

Krok trzeci w którym aktualizowana jest prędkość i pozycja każdej cząstki odpowiada za zdolność optymalizacji algorytmu PSO. Prędkość każdej cząstki w roju jest aktualizowana według wzoru:\\

\begin{center}
\begin{math}
v_{i}(t+1) = wv_{i} +c_{1}r_{1}[\hat{x_{i}}(t)-x_{i}(t)] +c_{2}r_{2}[g(t)-x_{i}(t)]
\end{math}
\end{center}
gdzie:

\begin{itemize}
\item i -- indeks cząstki
\item $v_{i}(t)$ -- prędkość cząstki i po czasie t
\item $x_{i}(t)$ -- pozycja cząstki  i po czasie t
\item w, c1, c2 -- współczynniki określane przez użytkownika, przy czym: \\$(0 \leqslant w \leqslant 1.2)$\\
$(0 \leqslant c_{1} \leqslant 2)$\\
$(0 \leqslant c_{2} \leqslant 2)$
\item $r_{1}, r_{2}$ -- wartości generowane losowo podczas każdej aktualizacji prędkości\\
$(0 \leqslant r_{1},r_{2} \leqslant 1)$
\item $\hat{x_{i}}(t)$ -- najlepsze indywidualne rozwiązanie kandydujące dla cząstki i po czasie t
\item $g(t)$ -- najlepsze globalne rozwiązanie kandydujące po czasie t
\end{itemize}

Każdy z trzech składników równania aktualizacji prędkości pełni inną rolę w algorytmie PSO. Pierwszy składnik $ wv_{i}$ to współczynnik inercji. Jest on odpowiedzialny za ruch cząstki w tym samym kierunku w którym wcześniej się poruszała. Wartość współczynnika inercji zazwyczaj waha się od 0.8 do 1.2. Może on przyspieszyć lub spowolnić cząstkę w jej pierwotnym kierunku. Niższe wartości współczynnika inercji przyspieszają zbieżność roju do optimum, natomiast wyższe wartości zachęcają do przeszukiwania całego obszaru poszukiwań.

Drugi współczynnik $c_{1}r_{1}[\hat{x_{i}}(t)-x_{i}(t)]$ zwany współczynnikiem poznawczym, służy jako pamięć cząstki, powodując, że cząstka ma skłonność do powrotu do obszarów gdzie doświadczyła wysokiego indywidualnego dopasowania. Współczynnik dopasowania $c_{1}$ zazwyczaj jest bliski 2 i ma wpływ na rozmiar kroku jaki cząstki przyjmują w kierunku najlepszego indywidualnego rozwiązania kandydującego $\hat{x_{i}}$.

Trzeci składnik $c_{2}r_{2}[g(t)-x_{i}(t)]$ nazywany składnikiem społecznym ma wpływ na ruch cząstki w kierunku najlepszego znalezionego przez rój regionu. Współczynnik społeczny $c_{2}$ jest zazwyczaj bliski 2 i wyraża rozmiar kroku jaki cząstka wykonuje w kierunku najlepszego globalnego rozwiązania kandydującego $g(x)$ jakie dotychczas udało się znaleźć rojowi.

Losowe wartości $r_{1}$ w współczynniku poznawczym oraz $r_{2}$ w współczynniku społecznym powodują, że te współczynniki mają stochastyczny wpływ podczas aktualizacji prędkości. Ta stochastyczna natura powoduje, że każda cząstka porusza się w częściowo przypadkowy sposób na który ogromny wpływ mają kierunki indywidualnych najlepszych rozwiązań cząstki i najlepsze globalne rozwiązanie roju.

Aby powstrzymać cząstki przed zbytnim oddaleniem się od obszaru poszukiwań, używamy techniki ograniczania maksymalnej prędkości cząstki. Dla obszaru poszukiwań ograniczonego do $[-x_{max},x_{max}]$, maksymalna prędkość cząstki jest ograniczona do $[-v_{max},v_{max}]$, gdzie $v_{max} = k \times x_{max}$. Wartość k to zdefiniowany przez użytkownika współczynnik maksymalnej prędkości, $0.1 \leqslant k \leqslant 1.0$. W wielu problemach optymalizacyjnych środek obszaru poszukiwań jest różny od początku układu współrzędnych i w związku z tym $[-x_{max},x_{max}]$ nie jest adekwatne do obszaru poszukiwań. W przypadku, gdy przestrzeń poszukiwań jest ograniczona przez $[x_{min},x_{max}]$ określamy $v_{max} = k \times (x_{max}-x_{min})/2$

Kiedy określimy prędkość każdej cząstki, pozycja każdej z nich jest aktualizowana poprzez zastosowanie prędkości do poprzedniej pozycji cząstki wg wzoru:
\begin{center}
$x_{i}(t+1)=x_{i}(t)+v_{i}(t+1)$
\end{center}
Cały proces jest powtarzany, aż zostanie spełniony warunek stopu. Typowe warunki stopu obejmują ilość iteracji algorytmu PSO, ilość iteracji od czasu ostatniej aktualizacji najlepszego globalnego rozwiązania kandydującego lub też zdefiniowanej wartości dopasowania.


\section{Dyskretna wersja PSO}

Dyskretny PSO zasadniczo różni się od pierwotnego (ciągłego) PSO w dwojaki sposób. Po pierwsze cząstka składa się z binarnych zmiennych. Po drugie szybkość cząstki musi być zamieniona na prawdopodobieństwo, że binarna zmienna przyjmie wartość 1.
 
Następująca notacja jest niezbędna w dyskretnym PSO. Oznaczmy przez $N_{p}$ liczbę cząstek w populacji. Niech $X_{i}^{t} = (x_{i1}^{t}, x_{i2}^{t}, ..., x_{iD}^{t}),  x_{id}^{t} \in \{0,1\}$ będzie cząstką i z D bitami w iteracji t, gdzie $X_{i}^{t}$ jest potencjalnym rozwiązaniem. Zmienia się ono z pewną szybkością. Oznaczmy tę szybkość jako  $V_{i}^{t} = (v_{i1}^{t}, v_{i2}^{t}, ..., v_{iD}^{t}),  v_{id}^{t} \in \mathbb{R}$ Niech  $P_{i}^{t} = (p_{i1}^{t}, p_{i2}^{t}, ..., p_{iD}^{t})$ będzie najlepszym rozwiązaniem jakie cząstka i pozyskała do iteracji t. Niech  $P_{g}^{t} = (p_{g1}^{t}, p_{g2}^{t}, ..., p_{gD}^{t})$ oznacza najlepsze rozwiązanie pozyskane z $P_{i}^{t}$ z populacji (gbest) lub od lokalnych sąsiadów (lbest) w iteracji t.

Podobnie jak w ciągłym PSO każda cząstka dopasowuje swoją szybkość zgodnie z częścią poznawczą oraz częścią społeczną:

\begin{center}
\begin{equation}
v_{id}^{t} = v_{id}^{t-1} + c_{1}r_{1}(p_{id}^{t} - x_{id}^{t}) + c_{2}r_{2}(p_{gd}^{t} - x_{id}^{t}),
\end{equation}
\end{center}

$v_{id}^{t}$ – szybkość cząstki w iteracji t – wpływ na nią ma poprzednia szybkość cząstki, część poznawcza oraz część społeczna\\
$c_{1}$ – współczynnik poznawczy\\
$c_{2}$  – współczynnik społeczny\\
$r_{1}, r_{2}$  – losowe liczby z przedziału [0;1]\\
$c_{k}r_{k} (k=1,2)$ – wartości mające wpływ na wagi obu części, gdzie zazwyczaj $c_{1}r_{1} + c_{2}r_{2} \leqslant 4$\\
Zgodnie z równaniem (1) każda cząstka porusza się zgodnie z jej nową szybkością. Dla wartości szybkości każdego bitu w cząstce wyższe wartości podwyższają prawdopodobieństwo 1, a mniejsze wartości zwiększają prawdopodobieństwo 0. Co więcej wartość szybkości ograniczona jest do przedziału $[0,1]$ przy użyciu następującej funkcji:\\
\begin{center}
\begin{equation}
s(v_{id}^{t}) = \frac{1}{1 + exp(-v_{id}^{t})}
\end{equation}
\end{center}


Gdzie $s(v_{id}^{t})$ oznacza prawdopodobieństwo, że bit $x_{id}^{t}$ przyjmie wartość 1. Aby uniknąć zbliżania się $s(v_{id}^{t})$ do 0 lub 1 używa się stałej $V_{max}$, żeby w praktyce ograniczyć zakres $v_{id}^{t}$ tzn. $v_{id}^{t} \in [-V_{max},+V_{max}]$. Zazwyczaj jako $V_{max}$ przyjmuje się 4.\\
Pseudokod dyskretnego PSO dla problemu maksymalizacji:\\

\noindent Powtarzaj

\noindent\ \ \ \ \textit{For i=1 to} $N_p$

\noindent\ \ \ \ \ \ \ \ If $G{(X}^t_i)>G(P^t_i)$ then   // G() oblicza funkcje celu

\noindent\ \ \ \ \ \ \ \ \ \ \ \ For d=1 to D bitów

\noindent\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $p^t_{id}=x^t_{id}$    // $p^t_{id}$ dotychczas najlepszy

\noindent\ \ \ \ \ \ \ \ \ \ \ \ Next d

\noindent\ \ \ \ \ \ \ \ End if

\noindent\ \ \ \ \ \ \ \ g=i      // dowolny

\noindent\ \ \ \ \ \ \ \ For j=indeksom sąsiadów (lub populacji)

\noindent\ \ \ \ \ \ \ \ \ \ \ \ If $G{(P}^t_j)>G(P^t_g)$ then g=j  // g to indeks najlepszej cząstki

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \   w populacji (lub sąsiedztwie)

\noindent\ \ \ \ \ \ \ \ Next j

\noindent\ \ \ \ \ \ \ \ For d=1 to D

\ \ \ \ \ \ \ \ $v^t_{id}=v^{t-1}_{id}+c_1r_1\left(p^t_{id}-x^t_{id}\right)+c_2r_2(p^t_{gd}-x^t_{id})$

\ \ \ \ \ \ \ \  $v^t_{id}\in \left[-V_{max},+V_{max}\right] $

\ \ \ \ \ \ \ \  If $losowa\ liczba<s\left(v^t_{id}\right)$ then $x^{t+1}_{id}=1$$;$ else $x^{t+1}_{id}=0$

\noindent\ \ \ \ \ \ \ \ Next d

\noindent\ \ \ \ Next i

\noindent Do spełnienia kryterium


\section{Proponowany algorytm PSO}
W tym rozdziale rozszerzymy dyskretny PSO tak aby rozwiązywał problem szeregowania zadań. Dyskretne wartości cząstki muszą być przemodelowane tak aby przedstawiały sekwencje n zadań. Także szybkość musi być zmieniona. Potrzebne jest także efektywne podejście do przesuwania cząstki do nowej sekwencji. Wygląda to następująco.

\subsection{Definicja dyskretnej cząstki}
 Tak w jak innych metaheurystykach rozwiązujących problem szeregowania zadań dużym problemem jest właściwa reprezentacja sekwencji n zadań w zmiennej. Definiujemy cząstkę i w iteracji t jako $X_{i}^{t} = (x_{i11}^{t}, x_{x12}^{t}, ..., v_{inn}^{t})$, gdzie $x_{ijk}$ równa się 1 jeżeli praca j cząstki i znajduje się na pozycji k-tej w sekwencji lub 0 w przeciwnym wypadku.

\subsection{Ścieżka szybkości}

 Definiujemy szybkość cząstki i w iteracji t jako $V_{i}^{t} = (v_{i11}^{t}, v_{i12}^{t}, ..., v_{inn}^{t}),  v_{ijk}^{t} \in \mathbb{R}$, gdzie $v_{ijk}^{t}$ jest wartością szybkości dla zadania j cząstki i znajdującej się na k-tej pozycji w iteracji t. Szybkość nazywana jest ścieżką szybkości. Wyższe wartości $v_{ijk}^{t}$ na ścieżce wskazują, że zadanie j będzie położone na k-tej pozycji z wyższym prawdopodobieństwem niż podczas niższych wartości.
 Nowa ścieżka szybkości cząstki jest aktualizowana zgodnie z poniższym równaniem:
\begin{center}
\begin{equation}
v_{ijk}^{t} = wv_{ijk}^{t-1} + c_{1}r_{1}(p_{ijk}^{t} - x_{ijk}^{t}) + c_{2}r_{2}(p_{gjk}^{t} - x_{ijk}^{t}),
\end{equation}
\end{center}

$P_{i}^{t} = (p_{i11}^{t}, p_{i12}^{t}, ..., p_{inn}^{t}),$ $p_{ijk}^{t} \in \{0,1\}$ oznacza najlepsze rozwiązanie jakie cząstka i znalazła do t-tej iteracji, $P_{g}^{t} = (p_{g11}^{t}, p_{g12}^{t}, ..., p_{gnn}^{t}),$ $p_{gjk}^{t} \in \{0,1\}$  oznacza najlepsze rozwiązanie pozyskane z cząstek populacji w t-tej iteracji. $w$ jest wagą bezwładności. Stała $V{max}$ jest używana do ograniczenia zakresu $v_{ijk}^{t}$.
 Tak jak w dyskretnym PSO wartości ścieżki szybkości muszą być przekonwertowane z liczb do zmian prawdopodobieństw wg wzoru:
\begin{center}
\begin{equation}
s(v_{ijk}^{t}) = \frac{1}{1 + exp(-v_{ijk}^{t})}
\end{equation}
\end{center}
Gdzie $s(v_{ijk}^{t})$ oznacza prawdopodobieństwo, że $v_{ijk}^{t}$ przyjmie wartość 1.

\subsection{Tworzenie sekwencji cząstki}
Każda cząstka tworzy nową sekwencję opartą o zmiany w prawdopodobieństwie w ścieżce szybkości. W konwencjonalnym podejściu cząstka i zaczyna z sekwencją null i przydziela zadanie j na pozycję k $(k=1,2,...,n)$ zgodnie z poniższym prawdopodobieństwem:
\begin{center}
\begin{equation}
q_{i}^{t}(j,k) = \frac{s(v_{ijk}^{t})}{\sum_{j \in U}s(v_{ijk}^{t}) }
\end{equation}
\end{center}
gdzie U jest zbiorem wszystkich nieprzydzielonych zadań. Kolejno dodawane są zadania do częściowej sekwencji dopóki ostateczna sekwencja nie zostanie zbudowana.
Aby obliczyć złożoność obliczeniową zamienimy U na mniejszy zbiór nieuszeregowanych zadań w algorytmie. Nowe prawdopodobieństwo:
\begin{center}
\begin{equation}
q_{i}^{t}(j,k) = \frac{s(v_{ijk}^{t})}{\sum_{j \in F}s(v_{ijk}^{t}) }
\end{equation}
\end{center}
gdzie F jest zbiorem pierwszych f nieuszeregowanych zadań obecnych w najlepszej dotychczas uzyskanej sekwencji. Jeżeli f jest mniejsze niż ilość nieuszeregowanych zadań to wszystkie zadania są uwzględnione.

\subsection{Wariant modelu gbest}
Dla sąsiedzkiej struktury cząstek w części społecznej modyfikujemy podejście do szukania $P_{g}^{t}$. W oryginalnej wersji $P_{g}^{t}$ jest uzyskiwane z $P_{i}^{t}$ $ (i=1,2,..., N_{p})$. Szukanie $P_{g}^{t}$  z obecnych cząstek $X_{i}^{t}$ $ (i=1,2,..., N_{p})$ zachowuje się lepiej.

\subsection{Proponowany algorytm PSO}

Pseudokod proponowanego algorytmu może wyglądać tak:\\

\noindent Zainicjalizuj parametry: $N_p,c_1,c_2,\omega ,V_{max},f,V_i=0$

\noindent Stwórz początkowe cząstki $X^1_i,i=1,\dots ,N_p$

\noindent Przypisz $P^1_i=X^1_i,B=X^1_1$   // B jest najlepszą sekwencją w algorytmie

\noindent Powtarzaj

\noindent \ \ \ // znajdź $P^t_i$

\noindent \ \ \ For i=1 to $N_p$

\noindent \ \ \  \ \ \ If $Z\left(X^t_i\right)\le Z\left(P^t_i\right)$ then   // Z() oblicza funkcję celu

\noindent \ \ \ \ \ \ \ \ \ $P^t_i=X^t_i$     // $P^t_i$ dotychczas najlepszy

\noindent \ \ \ \ \ \ End if

\noindent \ \ \ Next i

\noindent \ \ \ // znajdź $P^t_g$

\noindent \ \ \ g=1

\noindent \ \ \ For i=1 to $N_p$

\noindent \ \ \ If $Z\left(X^t_i\right)\le Z\left(P^t_g\right)$ then g=i  // g to indeks najlepszej cząstki w populacji

\noindent \ \ \ Next i

\noindent \ \ \ If $Z\left(P^t_g\right)\le Z\left(B\right)$ then B=$P^t_g$

\noindent \ \ \ // zaktualizuj ścieżkę szybkości

\noindent \ \ \ For i=1 to $N_p$

 \ \ \ \ \ \ $v^t_{ijk}=\omega v^{t-1}_{ijk}+c_1r_1\left(p^t_{ijk}-x^t_{ijk}\right)+c_2r_2(p^t_{gjk}-x^t_{ijk})$
 
  \ \ \ \ \ \ $v^t_{ijk}\in \left[-V_{max},+V_{max}\right]$
 
\noindent \ \ \ Next i

\noindent \ \ \ // tworzy nowe możliwe rozwiązanie

\noindent \ \ \ For i=1 to $N_p$

\noindent \ \ \ \ \ \ $O_i$ jest nullową sekwencją cząstki i

\noindent \ \ \ \ \ \ For k=1 to n-tej pozycji

\noindent \ \ \ \ \ \ \ \ \ // zmiana prawdopodobieństw

\noindent \ \ \ \ \ \ \ \ \ For j = indeksom F   // jeżeli F$<$f to wszystkie niezaplanowane

 \ \ \  \ \ \  \ \ \  \ \ \  \ \ \  \ \ \  \ \ \ zadania sa uwzględniane
 
 \ \ \ \ \ \ \ \ \ \ \ \ $s\left(v^t_{ijk}\right)=\frac{1}{1+{\rm exp}?(-v^t_{ijk})}$
 
\noindent \ \ \ \ \ \ \ \ \ Next j

\noindent \ \ \ \ \ \ \ \ \ // tworzenie

\noindent \ \ \ \ \ \ \ \ \ For j = indeksom F

\noindent \ \ \ \ \ \ \ \ \ \ \ \ $q^t_i\left(j,k\right)=\frac{s\left(v^t_{ijk}\right)}{\sum_{j\in F}{s\left(v^t_{ijk}\right)}}$

\noindent \ \ \ \ \ \ \ \ \ \ \ \ If $losowa\ liczba\le q^t_i\left(j,k\right)$

\noindent \ \ \ \ \ \ \ \ \ \ \ \  then zadanie j umieszczamy na k-tej pozycji w $O_i$$;$ idź do Nastepna\_Pozycja$;;$

\noindent \ \ \ \ \ \ \ \ \ Next j

\noindent \ \ \ \ \ \ \ \ \ Następna\_Pozycja

\noindent \ \ \ \ \ \  Next k

\noindent \ \ \ \ \ \  $X^{t+1}_i=O_i$

\noindent \ \ \ Next i

\noindent Do maksymalnej liczby iteracji

\section{Parametry}
W trakcie obliczeń algorytm przyjmuje domyślnie wartości parametrów zgodnie z poniższą specyfikacją:
\begin{itemize}
\item iterations = 1000
\item inertialWeight = 1.0
\item cognitionLearmningFactor  =  1.5
\item socialLearningFactor = 1.5
\item maxVelocity = 10.0
\item particlesNumber = 40
\end{itemize}


\section{Pomiary}
W poniższej tabeli zestawiono wyniki uzyskane przez opisywany algorytm z najlepszymi znanymi rozwiązaniami. Parametry algorytmu -- domyślne.

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline L. zadań & L.maszyn & Nr testu &  Wynik PSO & Najlepszy znany wynik & Błąd bezwzg.\\ 
\hline	20	&	5	&	1	&	1297	&	1278	&	1,49	\\ 
\hline	20	&	5	&	2	&	1366	&	1359	&	0,52	\\ 
\hline	20	&	5	&	3	&	1100	&	1081	&	1,76	\\ 
\hline	20	&	5	&	4	&	1309	&	1293	&	1,24	\\ 
\hline	20	&	5	&	5	&	1250	&	1235	&	1,21	\\ 
\hline	20	&	10	&	1	&	1600	&	1582	&	1,14	\\ 
\hline	20	&	10	&	2	&	1678	&	1659	&	1,15	\\ 
\hline	20	&	10	&	3	&	1534	&	1496	&	2,54	\\ 
\hline	20	&	10	&	4	&	1404	&	1377	&	1,96	\\ 
\hline	20	&	10	&	5	&	1456	&	1419	&	2,61	\\ 
\hline	20	&	20	&	1	&	2336	&	2297	&	1,70	\\ 
\hline	20	&	20	&	2	&	2149	&	2099	&	2,38	\\ 
\hline	20	&	20	&	3	&	2382	&	2326	&	2,41	\\ 
\hline	20	&	20	&	4	&	2246	&	2223	&	1,03	\\ 
\hline	20	&	20	&	5	&	2320	&	2291	&	1,27	\\ 
\hline	50	&	5	&	1	&	2730	&	2724	&	0,22	\\ 
\hline	50	&	5	&	2	&	2884	&	2834	&	1,76	\\ 
\hline	50	&	5	&	3	&	2646	&	2621	&	0,95	\\ 
\hline	50	&	5	&	4	&	2787	&	2751	&	1,31	\\ 
\hline	50	&	5	&	5	&	2887	&	2863	&	0,84	\\ 
\hline	50	&	10	&	1	&	3166	&	2991	&	5,85	\\ 
\hline	50	&	10	&	2	&	3035	&	2867	&	5,86	\\ 
\hline	50	&	10	&	3	&	2986	&	2839	&	5,18	\\ 
\hline	50	&	10	&	4	&	3196	&	3063	&	4,34	\\ 
\hline	50	&	10	&	5	&	3109	&	2976	&	4,47	\\ 
\hline	100	&	5	&	1	&	5527	&	5493	&	0,62	\\ 
\hline	100	&	5	&	2	&	5316	&	5268	&	0,91	\\ 
\hline	100	&	5	&	3	&	5265	&	5175	&	1,74	\\ 
\hline	100	&	5	&	4	&	5044	&	5014	&	0,60	\\ 
\hline	100	&	5	&	5	&	5311	&	5250	&	1,16	\\ 

\hline 
\end{tabular} 
\end{center}